The present invention relates generally to disk storage technology. More particularly, the invention relates to a set of improved disk scheduling and disk access algorithms for improving input/output performance. The improved algorithms may be used in a variety of disk access applications. They are particularly useful for multimedia servers which must supply video and audio streaming data in real time.
The use of multimedia servers has been growing rapidly as the public discovers more needs to store and retrieve different types of multimedia objects, e.g., text, images and video. For example, currently many state-of-the-art video editing stations use server-based technology to store and retrieve the multimedia content being worked on. Video on demand delivery systems also use similar server-based technology to deliver video to distribution sites or end user sites. As the Internet access bandwidth increases, server-based technology will be increasingly used to deliver multimedia content over that medium as well. Given adequate bandwidth, this multimedia content can be interactive—the user will be able to interact with and, to some extent control, what he or she sees.
The requirements to store and retrieve multimedia objects typically depends on the type of object being stored or retrieved. For real time streaming of video and audio data, many users require the data to be delivered within a specific deadline. If the server misses the deadline, and thus fails to deliver a particular video frame, that frame is no longer treated as needed. However, losing frames in video play back will result in jitters in the display. So real time applications, such as video playback, specify a performance guarantee, i.e. a data block should be available by a specific time. In contrast, a “best efforts” application, such as word processing application, does not typically require any performance guarantees. Thus deadline is an important parameter to consider when providing quality of service in a multimedia application; it is not so important in a word processing application.
Another important parameter for multimedia applications is priority. For example in a multimedia server application, different video clips might be assigned different priorities; and higher priority clips need preferential treatment over the lower priority ones. It is possible, for example, to devise a delivery system where premium subscribers get preferential treatment over non-premium subscribers. In a nonlinear video editing station, for example, certain critical editing operations may require high quality data feeds, whereas other less critical operations may be able to tolerate lower quality feeds.
Applications, such as real time multimedia delivery applications, that place attention on both deadline and priority have proven quite challenging for the designer of server-based storage and retrieval systems. Even with the today's high speed, high bandwidth server technology, there are still inherent tradeoffs in meeting both deadline and priority requirements. Which data is stored or retrieved first, and which data must be made to wait are fundamental issues that lie at the heart of many real time data delivery system designs. System designers employ various disk scheduling algorithms to handle these issues.
Prior approaches to disk access scheduling fall into two categories, based on whether the algorithm tries to minimize the disk seek time or tries to serve requests with deadline and priority requirements, treating the seek time as negligible compared to transfer time. Ignoring seek time is a valid assumption when we consider applications such as continuous media server, digital library or video editing system where clients make requests for data in large block sizes.
Some algorithms for multimedia applications employ cycle-based techniques designed to guarantee delivery of data in support of a jitter-free display. Cycle-based algorithms partition requests into groups and sort requests in each group according to the physical location of the data on the disk. They typically do not associate a deadline with the request. Instead, they break a cycle into slots, with each slot supporting a single display. Interactive applications are particularly challenging because users expect prompt response to their interactive input (similar to the response they experience when using other computer applications). Interactive application users notice excessive disk access latency immediately and do not like it. To address this, some have proposed offering higher performance level guarantees for interactive input requests than for more routine periodic requests.
Traditional deadline driven algorithms, such as Earliest Deadline First (EDF), SCAN-EDF and SCAN-RT, do not consider different priority levels. Instead they provide a soft real time delivery guarantee. One proposed variation of EDF with multiple queues takes into account of different priority levels. This variation of EDF has separate queues for each priority levels and requests are sorted according to deadlines in each priority queue. However, the algorithm used by this EDF variant will always take a request from the highest priority queue unless it is empty, in which case it will go to the next priority queue and so on. One disadvantage of this algorithm is that the low priority requests will suffer from starvation from this algorithm.
The present invention provides a set of algorithms to solve this starvation problem. The set of algorithms are deadline driven, but they also consider different priority levels. The algorithms will attempt to service a request with a lower priority and strict deadline only if serving this request is not going to violate the deadline constraints of a higher priority request. Two embodiments are illustrated and described. One embodiment uses a single queue to hold all the requests regardless of their priority. Another embodiment uses multiple queues. Each queue holds only requests with the same priority and the requests in each priority queue are sorted according to deadline.
For a more complete understanding of the invention, its objects and advantages, refer to the following specification and to the accompanying drawings.